import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

public class BinaryTree<T> implements iBinaryTree<T> {

    /* 此树为二叉链表实现 */
    BinaryNode<T> root = null;

    // 无参构造
    BinaryTree() {

    }

    // 序列构造
    BinaryTree(T[] source) {
        this.root = prebuild(source);
    }

    private int i = 0;

    // 先根序指定构造递归单元
    private BinaryNode<T> prebuild(T[] source) {
        BinaryNode<T> p = null;
        if (i < source.length) {
            T element = source[i++];
            if (!element.equals("#")) {
                p = new BinaryNode<T>(element);
                p.left = prebuild(source);
                p.right = prebuild(source);
            }
        }
        return p;
    }

    @Override
    public BinaryNode<T> getParent(BinaryNode<T> child) {
        BinaryNode<T> par = null;
        Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();
        BinaryNode<T> p = this.root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                if (p.left == child) {
                    par = p;
                    break;
                } else {
                    stack.push(p);
                    p = p.left;
                }
            } else {
                p = stack.pop();
                p = p.right;
            }
        }
        return par;
    }

    @Override
    public BinaryNode<T> getChild(BinaryNode<T> parent, boolean isLChild) {
        return isLChild ? parent.left : parent.right;
    }

    @Override
    public boolean isEmpty() {
        return root == null;
    }

    @Override
    public void insert(T x) {
        if (x != null) {
            this.root = new BinaryNode<T>(x, this.root, null);
        }
    }

    @Override
    public BinaryNode<T> insert(BinaryNode<T> p, boolean left, T x) {
        if (p == null || x == null) {
            return null;
        } else {
            if (left) {
                p.left = new BinaryNode<T>(x, p.left, null);
                return p.left;
            } else {
                p.right = new BinaryNode<T>(x, null, p.right);
                return p.right;
            }
        }
    }

    @Override
    public void remove(BinaryNode<T> p, boolean isleft) {
        if (p.data != null) {
            if (isleft) {
                p.left = null;
            } else {
                p.right = null;
            }
        }
    }

    @Override
    public void remove(T key) {
        Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();
        BinaryNode<T> p = this.root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                if (p.data.equals(key)) {
                    p.left = null;
                    p.right = null;
                    break;
                } else {
                    stack.push(p);
                    p = p.left;
                }
            } else {
                p = stack.pop();
                p = p.right;
            }
        }
    }

    @Override
    public void clear() {
        this.root = null;
    }

    @Override
    public void preorder() {
        preorder(this.root);
        System.out.println();
    }

    @Override
    public void inorder() {
        inorder(this.root);
        System.out.println();
    }

    @Override
    public void postorder() {
        postorder(this.root);
        System.out.println();
    }

    @Override
    public void preorder(BinaryNode<T> p) {
        if (p != null) {
            System.out.print(p.data.toString() + "\t");
            preorder(p.left);
            preorder(p.right);
        }
    }

    @Override
    public void inorder(BinaryNode<T> p) {
        if (p != null) {
            inorder(p.left);
            System.out.print(p.data.toString() + "\t");
            inorder(p.right);
        }
    }

    @Override
    public void postorder(BinaryNode<T> p) {
        if (p != null) {
            postorder(p.left);
            postorder(p.right);
            System.out.print(p.data.toString() + "\t");
        }
    }

    @Override
    public void preorderTraverse() {
        Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();
        BinaryNode<T> p = this.root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                System.out.print(p.data.toString() + "\t");
                stack.push(p);
                p = p.left;
            } else {
                System.out.println("^ ");
                p = stack.pop();
                p = p.right;
            }
            System.out.println("^ ");
        }
    }

    @Override
    public void levelorder() {
        Queue<BinaryNode<T>> que = new LinkedBlockingQueue<BinaryNode<T>>();
        que.add(this.root);
        while (!que.isEmpty()) {
            BinaryNode<T> p = que.poll();
            System.out.print(p.data.toString() + "\t");
            if (p.left != null) {
                que.add(p.left);
            }
            if (p.right != null) {
                que.add(p.right);
            }
        }
        System.out.println();
    }

    @Override
    public int size() {
        Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();
        BinaryNode<T> p = this.root;
        int num = 0;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                num++;
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                p = p.right;
            }
        }
        return num;
    }

    @Override
    public int height() {
        if (root == null) {
            return 0;
        } else {
            int l = this.height(root.left);
            int r = this.height(root.right);
            return l > r ? l + 1 : r + 1;
        }
    }

    public int height(BinaryNode<T> root) {
        if (root == null) {
            return 0;
        } else {
            int l = this.height(root.left);
            int r = this.height(root.right);
            return l > r ? l + 1 : r + 1;
        }
    }

    @Override
    public BinaryNode<T> search(T key) {
        Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();
        BinaryNode<T> p = this.root;
        BinaryNode<T> target = null;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                if (p.data.equals(key)) {
                    target = p;
                    break;
                }
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                p = p.right;
            }
        }
        return target;
    }

    @Override
    public int level(T key) {
        if (key == null) {
            return -1;
        } else if (root == null) {
            return 0;
        } else if (key.equals(root.data)) {
            return 1;
        } else {
            int l = this.level(root.left, key);
            int r = this.level(root.right, key);
            return l > r ? l + 1 : r + 1;
        }
    }

    public int level(BinaryNode<T> root, T key) {
        if (key == null) {
            return -1;
        } else if (root == null) {
            return 0;
        } else if (key.equals(root.data)) {
            return 1;
        } else {
            int l = this.level(root.left, key);
            int r = this.level(root.right, key);
            return l > r ? l + 1 : r + 1;
        }
    }

    @Override
    public int leaf() {
        if (root == null) {
            return 0;
        }
        Queue<BinaryNode<T>> que = new LinkedBlockingQueue<BinaryNode<T>>();
        que.add(root);
        int sum = 0;
        BinaryNode<T> p = null;
        while (!que.isEmpty()) {
            p = que.poll();
            if (p.isLeaf()) {
                sum++;
            } else {
                if (p.left == null) {
                    que.add(p.left);
                }
                if (p.right == null) {
                    que.add(p.right);
                }
            }
        }
        return sum;
    }
}